package com.tanzc.sort;

import com.tanzc.util.ArrayUtils;

import java.util.Date;

/**
 * <p> description: 归并排序</p>
 *
 * @author tanzc
 * @date 2021/12/30
 **/
public class MergeSort {
    public static void main(String[] args) {
        MergeSort mergeSort = new MergeSort();
        int num = 10000000, max = num * 5;
        int[] arr = ArrayUtils.random(num, max);
//        int[] arr = ArrayUtils.worst(num);
//        int[] arr = ArrayUtils.bad(num);
//        int[] arr = ArrayUtils.nice(num);

        int[] arr1 = new int[num];
        System.arraycopy(arr, 0, arr1, 0, num);
//        ArrayUtils.printArray(arr1);

        System.out.print("归并排序-----time: ");
        Date start = new Date();
        int[] result = mergeSort.merge(arr1);
        Date end = new Date();
        long timediff = end.getTime() - start.getTime();
        System.out.println(timediff + "ms");
//        ArrayUtils.printArray(result);
    }

    /**
     * 归并排序，所谓归并，就是将多个序列归为一个序列
     * 归并排序采用分治法，每个序列可以分成左右两个序列，或多个序列。这些子序列排序好后，再进行归并，得出当前序列的有序序列
     * 序列的拆分一直到序列长度为1，此时序列有序，然后向上归并
     * 具体的归并操作为----两序列合并，
     * 由于归并的子序列已有序，所以两序列的合并只需要每次把较小元素放进新序列即可，然后返回有序的新序列
     * @param arr
     * @return
     */
    public int[] merge(int[] arr) {
        if (arr.length < 2) {
            return arr;
        }
        // 拆分子序列
        int middle = arr.length / 2;
        int[] left = new int[middle];
        int[] right = new int[arr.length - middle];
        System.arraycopy(arr, 0, left, 0, middle);
        System.arraycopy(arr, middle, right, 0, arr.length - middle);
        // 子序列有序后，归并左右序列
        return mergeSort(merge(left), merge(right));
    }

    public int[] mergeSort(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int l = 0, r = 0, k = 0;
        // 对两序列从左到右依次遍历，每次取最小的放进新序列
        while (l < left.length && r < right.length) {
            if (left[l] <= right[r]) {
                result[k++] = left[l++];
            } else {
                result[k++] = right[r++];
            }
        }
        if (l < left.length) {
            while (l < left.length) {
                result[k++] = left[l++];
            }
        } else if (r < right.length){
            while (r < right.length) {
                result[k++] = right[r++];
            }
        }

        return result;
    }


}
